﻿// 0914train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

/*
 为了便于业务交互，约定一个对输入的字符串中的下划线做统一替换
具体要求L对于给定的输入字符串，将其中包含的每一个下划线"_"
使用特殊字符串"(^|$|[,+])"替换，并输出替换后的结果
其中的例外场景不做替换，场景如下：
1.在一堆方括号之内的下划线则不替换
2.为转义的下划线，即"\_"则不替换

备注：
1.调用者已经保证，输入表达式的方括号会成对出现，并且方括号会存在嵌套。即存在"[xx[yyyy]xxx]"这种形式的字符串
2.输入字符串的长度范围：[0, 10000]
示例1
输入
"^(_9494)"
输出
"^((^|$|[,+])9494)"


"^(\_9494)"
"[xx_[yyyy_]xxx_]_"
 */
class Solution01
{
public:
    Solution01(string&origin_str)
    {
        int square_count = 0; //左括号+1，右括号-1，大于1说明在括号内

        string replace_str = "(^|$|[,+])";
        //遇到斜杠，判断下个是否是_，是的话i+=2
        int str_size = origin_str.size();
        int index = 0;

        string result;
        while (index<str_size)
        {
            char curr_char = origin_str[index];

            //即"\_"则不替换
            if (curr_char=='\\')
			{
                if (index+1<str_size && origin_str[index+1]=='_')
                {
                    result += curr_char;
                    result += origin_str[index + 1];
                    index += 2;
                    continue;
                }
			}
            if (curr_char=='[')
            {
                square_count += 1;
            }
            else if (curr_char==']')
            {
                square_count -= 1;
            }
            else if (curr_char=='_')
            {
                if (square_count==0)
                {
                    //不在括号中
                    result += replace_str;
                    index++;
                    continue;
                }

            }

            result += curr_char;
            index++;
            //while
        }
        cout << result;
	    //Solution01
    }
};


/*
 手上有一副扑克牌，每张牌按牌面数字记分（J=11,Q=12,K=13，没有大小王)，出牌时按照以下规则记分：
出单张，记牌面分数，例如出一张2，得分为2
出对或3张，记牌面分数总和再x2，例如出3张3，得分为(3+3+3)x2=18
出5张顺，记牌面分数总和再x2，例如出34567顺，得分为(3+4+5+6+7)x2=50
出4张炸弹，记牌面分数总和再x3，例如出4张4，得分为4x4x3=48
求出一副牌最高的得分数。

输入描述
按顺序排好的一副牌，最少1张，最多15张。
1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK.
无需考虑输入非法的情况，例如输入字符不在[0-9JQK]范围或某一张牌超过4张
输出描述
最高的得分数
备注
积分规则中没有的出牌方式不支持，例如不支持3带1、4带2，不支持5张以上的顺，且10JQKA(OJQK1)不算顺.

示例1：
输入：
33445677

输出
67
说明
出对3、对4、对7，单张5、6，得分为67
出34567顺，再出单张3、4、7，得分为64输出结果67因此最高得分是按对出，
可得到最高分67
 */
class Solution02
{
public:
    string translateCard(string&card_str)
    {
        if (card_str == "0") return "10";
        if (card_str == "10") return "0";

        //J=11,Q=12,K=13
        if (card_str == "J") return "11";
        if (card_str == "11") return "J";

        if (card_str == "Q") return "12";
        if (card_str == "12") return "Q";

        if (card_str == "K") return "13";
        if (card_str == "13") return "K";

        return card_str;
        //translateCard
    }

    int getConstrain()
    {
        //计算全组顺子的分数
        int curr_score = 0;

        for (int i = 1; i <= 9; i++)
        {
            while (card_vec[i] > 0)
            {
                vector<int>track;
                track.push_back(i);
                for (int next=i+1; next<card_vec.size(); next++)
                {
                    if (track.size() == 5) break;
                    if (card_vec[next]>0)
                    {
                        track.push_back(next);
                    }
                }
                if (track.size()==5)
                {
                    //组成
                    //出5张顺，记牌面分数总和再x2
                    int score = 0;
                    for (auto&num:track)
                    {
                        score += num * 2;
                        card_vec[num] -= 1;
                    }
                    curr_score += score;
                }
                else
                {
                    break;
                }
                //尝试组顺子-----
            }

            //for
        }


        return curr_score;
    }

    int getCombine()
    {
        //计算组单的分数
        int curr_score = 0;

        for (int i=1; i<=13; i++)
        {
            int count = card_vec[i];
            if (count ==1)
            {
                //记牌面分数
                curr_score += i;
            }
            else if (count == 2|| count ==3)
            {
                //出对或3张*2
                curr_score += i * 2 * count;
            }
            else if (count == 4)
            {
                //出4张炸弹，记牌面分数总和再x3
                curr_score += i * 3 * count;
            }
        }

        return curr_score;
    }

    Solution02(string&num_str)
    {
        card_vec.resize(14); //最大K 13
        //1-9输入为数字1-9，10输入为数字0，JQK输入为大写字母JQK
        for (auto&ch:num_str)
        {
            string card_str;
            card_str += ch;
            string card_num_str = translateCard(card_str);
            int card_num = stoi(card_num_str);
            card_vec[card_num] += 1;
        }
        origin_vec = card_vec;
        //1先查看能否组顺子，组完顺子，更新出对的分数
        int constrain_score = getConstrain();
        int combine_score = getCombine();
        total_score = constrain_score + combine_score;

        //2直接全部出对，查看分数
        //重置下card_vec
        card_vec = origin_vec;
        int total_combine = getCombine();
        total_score = max(total_score, total_combine);
        
        cout << total_score;

        //Solution02
    }
private:
    int total_score = 0;
    vector<int>card_vec;
    vector<int>origin_vec;
};

/*
 素数之积
 输入
 15
 输出
 3 5
 */
class Solution03
{
public:
    void initPrimeSt(int num, vector<bool>&num_prime_st)
    {
        num_prime_st[0] = false;
        num_prime_st[1] = false;

        for (int i = 2; i * i <= num; i++)
        {
            if (num_prime_st[i])
            {
                //i是质数，i的倍数全不为质数
                for (int next = i * 2; next <= num; next += i)
                {
                    num_prime_st[next] = false;
                }
            }
        }
        //initPrimeSt
    }
    Solution03(int num)
    {
        vector<bool>num_prime_st(num + 1, true);
        initPrimeSt(num, num_prime_st);

        
        int res_1 = -1, res_2 = -1;
        for (int i=2; i*i<=num; i++)
        {
            if (num_prime_st[i] && num%i==0)
            {
                int other = num / i;
                if (num_prime_st[other])
                {
                    res_1 = i;
                    res_2 = other;
                    break;
                }
            }
        }
        
        cout << res_1 << ' ' << res_2;
           
        //Solution03
    }

};


/*
有 10 名游戏爱好者参与，分为两队，每队 5 人。
每位参与者都有一个评分，代表着他的游戏水平。
为了表演赛尽可能精彩，我们需要把 10 名参赛者分为实力尽量相近的两队。一队的实力可以表示为这一队 5 名队员的评分总和。
现在给你 10 名参与者的游戏水平评分，请你根据上述要求分队最后输出这两组的实力差绝对值。
例: 10 名参赛者的评分分别为 5 1 8 3 4 6 7 10 9 2，分组为 (1 3 5 8 10) (2 4 6 7 9)，两组实力差最小，差值为 1。有多种分法，但实力差的绝对值最小为 1。
输入描述
10 个整数，表示 10 名参与者的游戏水平评分。范围在[1,10000]之间

输出描述
1 个整数，表示分组后两组实力差绝对值的最小值

输入
1 2 3 4 5 6 7 8 9 10
输出
1
 */
class Solution04
{
public:
    void backTrack(vector<int>& num_vec, int start)
    {
        if (track.size()==sub_size)
        {
            int sum = 0;
            for (auto&num:track)
            {
                sum += num;
            }
            result.push_back(sum);
            return;
        }

        for (int i=start; i<num_vec.size(); i++)
        {
            track.push_back(num_vec[i]);
            backTrack(num_vec, i + 1);
            track.pop_back();
        }
    }
    Solution04(vector<int>&num_vec)
    {
        int total_sum = 0;
        for (auto&num:num_vec)
        {
            total_sum += num;
        }

        for (int i=0; i<num_vec.size(); i++)
        {
            track.push_back(num_vec[i]);
            backTrack(num_vec, i + 1);
            track.pop_back();
        }

        int min_diff = INT_MAX;
        for (auto&num:result)
        {
            int other = total_sum - num;
            int curr_diff = abs(other - num);
            min_diff = min(min_diff, curr_diff);
        }

        cout << min_diff;
        //Solution04
    }
private:
    int sub_size = 5;
    vector<int>track;
    vector<int>result;
};

/*
有一辆汽车需要从 m*n 的地图的左上角(起点)开往地图的右下角(终点)，
去往每一个地区都需要消耗一定的油量，加油站可进行加油

请你计算汽车确保从起点到达终点时所需的最少初始油量说明:
(1) 智能汽车可以上下左右四个方向移动1
(2) 地图上的数字取值是 0或-1 或者正整数:
-1: 表示加油站，可以加满油，汽车的油箱容量最大为 100;
0: 表示这个地区是障碍物，汽车不能通过
正整数: 表示汽车走过这个地区的耗油量
(3) 如果汽车无论如何都无法到达终点，则返回 -1


输入描述
第一行为两个数字，M，V，表示地图的大小为 M,N(0< M,N < 200)

后面一个M*N 的矩阵，其中的值是 0 或 -1 或正整数，加油站的总数不超过 200个
输出描述
如果汽车无论如何都无法到达终点，则返回-1
如果汽车可以到达终点，则返回最少的初始油量


示例1
输入
2,2
10,20
30,40
输出
70

示例2
输入
4,4
10,30,30,20
30,30,-1,10
0,20,20,40
10,-1,30,40
输出
70

示例3
输入

4,5
10,0,30,-1,10
30,0,20,0,20
10,0,10,0,30
10,-1,30,0,10
输出
60

示例4
输入
4,4
10,30,30,20
30,30,20,10
10,20,10,40
10,20,30,40
输出
-1
 */
class Solution05
{
public:
    struct Node
    {
        int val, row, col;
        Node() = default;
        Node(int val, int row, int col) :val(val),row(row),col(col) {};
        bool operator<(const Node&other) const
        {
            if (val==other.val)
            {
	            if (row==other.row)
	            {
                    //顶部最大
                    return col < other.col;
	            }
                //顶部最大
                return row < other.row;
            }
            //从小到大，顶部最小
            return val > other.val;
        }
    };
    Solution05(vector<vector<int>>&grid)
    {
        if (grid.empty())
        {
            cout << -1;
            return;
        }

        //0或-1 或者正整数
        //0不能通过
        row_size = grid.size();
        col_size = grid[0].size();
        vector<vector<bool>>checked(row_size, vector<bool>(col_size, false));

        Node first_node(grid[0][0], 0, 0);
        priority_queue<Node>exec_queue;
        exec_queue.push(first_node);
        //标记已访问
        checked[0][0] = true;

        bool is_end = false;
        while (!exec_queue.empty())
        {
            Node top_node = exec_queue.top();
            exec_queue.pop();
            track.push_back(top_node.val);

            for (auto&dir_vec:DirectionGrid)
            {
                int curr_r = top_node.row + dir_vec[0];
                int curr_c = top_node.col + dir_vec[1];

                if (curr_r==row_size-1 && curr_c==col_size-1)
                {
                    track.push_back(grid[curr_r][curr_c]);
                    is_end = true;
                    break;
                }

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r&&is_curr_c)
                {
                    bool is_visited = checked[curr_r][curr_c];
                    bool is_available = grid[curr_r][curr_c] != 0;

                    if (!is_visited&&is_available)
                    {
                        Node next_node(grid[curr_r][curr_c], curr_r, curr_c);
                        exec_queue.push(next_node);
                        //标记已访问
                        checked[curr_r][curr_c] = true;
                    }
                }

                //dir_vec
            }
            if (is_end) break;
            //while
        }

        if (!is_end)
        {
            cout << -1;
            return;
        }

        int result = 0;
        int curr_cost = 0;
        bool is_available = true;
        bool is_pre_add = false;
        for (auto&num:track)
        {
            if (curr_cost>100)
            {
                is_available = false;
                break;
            }

            if (num==-1)
            {
                if (!is_pre_add)
                {
                    result += curr_cost;
                }
                is_pre_add = true;
                curr_cost = 0;
            }
            else
            {
                curr_cost += num;
            }
        }
        

        if (!is_available)
        {
            cout << -1;
            return;
        }

        if (result == 0)
        {
            result = curr_cost;
        }

        if (result<=100)
        {
            cout << result;
        }
        else
        {
            cout << -1;
        }

        //Solution05
    }
private:
    vector<int>track;
    int row_size = 0, col_size = 0;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};

int main()
{
	{
        string row_col;
        getline(cin, row_col);
        vector<int>row_col_vec;
        stringstream sstream_1(row_col);
        string token;

        while (getline(sstream_1, token,','))
        {
            row_col_vec.push_back(stoi(token));
        }
        int row_size = 0;
        if (!row_col_vec.empty())
        {
            row_size = row_col_vec[0];
        }

        vector<vector<int>>grid;
        string input;
        for (int r=0; r<row_size; r++)
        {
            vector<int>row_vec;
            getline(cin, input);
            stringstream sstream_2(input);

            while (getline(sstream_2,token,','))
            {
                row_vec.push_back(stoi(token));
            }
            grid.push_back(row_vec);
        }
        
        Solution05 solu(grid);
        return 0;
	}
	{
        vector<int>num_vec(10);

        for (int i=0; i<num_vec.size();i++)
        {
            cin >> num_vec[i];
        }

        Solution04 solu(num_vec);

        return 0;
	}
	{
        int num;
        cin >> num;

        Solution03 solu(num);

        return 0;
	}
	{
        string num_str;
        cin >> num_str;
        //33445677JQK
        Solution02 solu(num_str);

        return 0;
	}
    string input;
    getline(cin, input);

    Solution01 solu(input);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
